//给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。 
//
// 当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。 
//
// 请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。 
//
// 注意：不允许旋转信封。 
// 
//
// 示例 1： 
//
// 
//输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
//输出：3
//解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。 
//
// 示例 2： 
//
// 
//输入：envelopes = [[1,1],[1,1],[1,1]]
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= envelopes.length <= 10⁵ 
// envelopes[i].length == 2 
// 1 <= wi, hi <= 10⁵ 
// 
// Related Topics数组 | 二分查找 | 动态规划 | 排序 
//
// 👍 773, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.Arrays;

class RussianDollEnvelopes {
    public static void main(String[] args) {
        Solution solution = new RussianDollEnvelopes().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 参照labuladong：https://labuladong.gitee.io/algo/3/25/70/
        public int maxEnvelopes(int[][] envelopes) {
            Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
            int[] heights = new int[envelopes.length];
            for (int i = 0; i < envelopes.length; i++) {
                heights[i] = envelopes[i][1];
            }

            return lengthOfLIS(heights);
        }

        // 一维数组寻找最大子序列
        // TLE
        /*public int lengthOfLIS(int[] nums) {
            int[] dp = new int[nums.length];
            Arrays.fill(dp, 1);
            int res = 0;
            for (int i = 0; i < nums.length; i++) {
                for (int j = 0; j < i; j++) {
                    if (nums[i] > nums[j]) {
                        dp[i] = Math.max(dp[j] + 1, dp[i]);
                    }
                }
                res = Math.max(res, dp[i]);
            }

            return res;
        }*/

        // 二分法分堆来解题：https://labuladong.gitee.io/algo/3/25/70/
        public int lengthOfLIS(int[] nums) {
            int[] top = new int[nums.length];
            int piles = 0;  // 堆数
            for (int i = 0; i < nums.length; i++) {
                // 要处理的扑克牌
                int poker = nums[i];
                // 找到最左侧放入的堆
                int l = 0, r = piles;
                while (l < r) {
                    int mid = l + (r - l) / 2;
                    if (top[mid] > poker) {
                        r = mid;
                    } else if (top[mid] < poker) {
                        l = mid + 1;
                    } else {
                        r = mid;
                    }
                }

                // 没有堆满足，则新建堆
                if (l == piles) piles++;
                // 更新堆顶
                top[l] = poker;
            }

            // 堆数就是最大递增子序列
            return piles;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
